\section{Problema 3}

\subsection{Introducci\'on}
En este ejercicio, se plantea encontrar la secuencia de cortes de costo mínimo en un listón de madera de longitud dada. Dicho listón tiene cortes predefinidos a realizar en el mismo. Cada corte a realizar en dicho listón, tendrá un costo asociado, y el objetivo es encontrar la secuencia de cortes, tal que la suma de los costos de esos cortes, sea mínima. Los costos asociados a cada corte, deben considerarse proporcionales a la longitud del listón que se está cortando en ese momento. Es decir, a mayor largo del listón, mayor es el costo para realizar el corte.\\

Se debe leer de un archivo de entrada, distintas instancias del problema, las cuales están constituídas por un valor que representa el largo del listón, y una secuencia de valores, que representan los puntos en donde se debe realizar los cortes. Se debe calcular y devolver la secuencia ordenada de cortes, tal que la suma de los subcostos de realizarlos, sea mínima.\\

	   
\subsection{Desarrollo}

Primeramente, se asume que el costo asociado a cortar un listón de longitud \textit{n}, es precisamente \textit{n}. De esta manera, nos aseguramos de estar cumpliendo la condición, de que el costo de cortar un listón, es proporcional a la longitud de dicho listón.

Para resolver este problema, se decidió utilizar el método de \textit{Programaci\'on din\'amica}\footnote{http://en.wikipedia.org/wiki/Dynamic\_programming} , usando una matriz para calcular los costos. Consideramos, que el costo mínimo de efectuar los cortes en un sublistón cualquiera del listón principal, es una subestructura óptima del problema, y que podemos usar estos subresultados óptimos, para calcular el resultado óptimo del problema principal, es decir, el costo mínimo de realizar los cortes del listón original.\\ 
La idea, consiste en ir precalculando el costo mínimo de realizar cortes en un sublistón, para luego poder usarlo mas adelante, en caso de ser necesario.\\
La forma en que el algoritmo usará la matriz, es la siguiente: dados \textit{n} cortes a realizar en el listón, se creará una matriz de \textit{n+2} filas y \textit{n+2} columnas. Esto se debe a que, agregaremos dos cortes ``ficticios" mas al listón, estos serán el comienzo del listón, y el fin del mismo respectivamente, es decir los extremos.\\
Sea \textbf{M} la matriz de costos asociados, definimos a \textit{M[i,j]} como el costo mínimo de realizar cortes dentro del listón comprendido por los cortes \textit{i} y \textit{j}. Por ejemplo, \textit{M[2,4]} almacenará el costo mínimo de realizar cortes en el sublistón entre el corte \textit{2} y \textit{4}, y \textit{M[0,3]} tendrá el cálculo de esa operación entre el comienzo del listón total y el corte 3, y así sucesivamente. De esta definición, podemos deducir que \textit{M[i,j] = M[j,i]}, $\forall i,j,  0 \leq i, j \leq n+1$. Es decir, el costo mínimo de realizar cortes entre \textit{i} y \textit{j}, es el mismo que realizar cortes en el listón entre \textit{j} e \textit{i}, ya que es el mismo listón. Por esto mismo, no se rellenará la matriz en su totalidad, sino que solo se usará la parte triangular superior de la matriz. Por definición de esta misma estrategia, sabemos que el resultado buscado, siempre se encontrará en la posición \textit{M[0,n+1]} de la matriz, ya que representa el costo mínimo entre los extremos del listón total.\\

Para las posiciones de la matriz, se cumplen las siguientes condiciones:
\begin{itemize}
\item Caso especial: $\forall i, M[i][i] = UNDEFINED$, tal que  $0 \leq i \leq n+1$, ya que no hay listón.
\item Caso base: $\forall i M[i][i+1] = 0$, tal que  $0 \leq i, \leq n+1$, ya que en el listón, no hay cortes a realizar.
\item Caso recursivo: $(\forall i, j$, tal que $j \geq i +2$,  $M[i][j] = cortes[j]-cortes[i] + min (M[i][k], M[k][j]) (\forall k$, $i < k < j))$, aquí se calcula el costo minimo, del listón, teniendo en cuenta todos sus cortes internos.

\end{itemize}
Ademas de almacenar en cada posición de la matriz los costos mínimos por listón, tambien debemos almacenar las secuencias de cortes óptimos asociadas, ya que esto se necesita para poder devolver el resultado. Debido a esto la matriz es una matriz que almacena instancias de la clase \textit{RibbonData}\footnote{ribbon = listón}, para poder tener toda esta información útil, a la hora de usarla.



\newpage

\subsection{Pseudoc\'odigo}
En el archivo \textbf{Ej3.java} podremos encontrar la clase ``Ej3'' con las funciones para resolver el problema.

Existe una clase/estructura llamada \textit{RibbonData}, la cual estará formada por un entero \textit{minCost} y un vector de enteros \textit{optimalCuts}. Estos datos corresponden al minímo costo asociado a un sublistón y a la secuencia óptima de cortes para ese listón, respectivamente.\\
Se asume que hay \textit{n} cortes a realizar en el listón original.

\begin{itemize}
\item $Vector<Integer>$ cuts : Contiene los cortes a realizar en el listón.
\item $RibbonData[][]$ minCostsMatrix : Una matriz para hacer los calculos de costo mínimo, junto con los cortes óptimos asociados.
\item $Vector<Integer>$ bestCutSequence : Es la secuencia óptima de cortes, el resultado a devolver.
\end{itemize}

\begin{parr}
\begin{algorithm}[H]
\caption{\operMA{Ej3}{ \vin{ribbonLenght}{int}, \vin{cuts}{Vector$<$Integer$>$}}} 
\begin{algorithmic}[1]\parskip=1mm
\STATE \textbf{//En el siguiente paso se agrega 2 cortes ``ficticios''al listón}
\STATE cuts.AgregarAlPrincipio(0)
\STATE cuts.AgregarAlFinal(ribbonLenght)
\STATE \textbf{//Inicialización de la matriz}
\STATE initMatrix()
\STATE \textbf{//se realiza todos los cálculos sobre la matriz}
\STATE calculateCosts()
\STATE \textbf{//Se asigna el resultado a devolver a la variable correspondiente}
\STATE bestCutSequence $\leftarrow$ minCostsMatrix$[$0$][n+1]$.optimalCuts
\end{algorithmic}
\end{algorithm}
\end{parr}

En la función \textit{initMatrix}, se inicializan los datos de la matriz. Notar, que entre dos cortes contiguos, no es necesario realizar cortes, por ende su costo es 0, y en todas las posiciones involucradas se procede a inicializar con 0.

\begin{parr}
\begin{algorithm}[H]
\caption{\operMA{initMatrix}{}}
\begin{algorithmic}[1]\parskip=1mm
\STATE minCostsMatrix $\leftarrow$ RibbonData$[n+2][n+2]$

\STATE \textbf{//Inicialización de la matriz}
\FOR {i desde 0 hasta  n$+$1}
\FOR {j desde 0 hasta n$+$1}
\STATE minCostsMatrix$[$i$][$j$].minCost$ $\leftarrow UNDEFINED$
\STATE minCostsMatrix$[$i$][$j$].optimalCuts \leftarrow VectorVacio$
\ENDFOR 
\ENDFOR

\STATE \textbf{//Para toda posición i,i+1 de la matriz, se le asocia un costo 0}
\FOR {i desde 0 hasta n$+$1 }
\STATE minCostsMatrix$[$i$][$i $+$ 1$].minCost$ $\leftarrow$ 0
\ENDFOR
\end{algorithmic}
\end{algorithm}
\end{parr}

En \textit{calculateCosts} se pide el costo del listón completo, esto disparará las llamadas recursivas.

\begin{parr}
\begin{algorithm}[H]
\caption{\operMA{calculateCosts}{}}
\begin{algorithmic}[1]\parskip=1mm
\STATE calculateCost$(0, minCostsMatrix.longitud - 1)$;
\end{algorithmic}
\end{algorithm}
\end{parr}

\newpage

Se calcula el costo mínimo entre dos cortes, haciendo llamadas recursivas.

\begin{parr}
\begin{algorithm}[H]
\caption{\operL{calculateCost}{\vin{i}{int}, \vin{j}{int}}{int}}
\begin{algorithmic}[1]\parskip=1mm
\IF {minCostsMatrix$[$i$][$j$].minCost $==$ UNDEFINED$}
\STATE minCostsMatrix$[i][j].minCost$ $\leftarrow$ cuts[j] $-$ cuts[i] $+$ minCost(i, j)
\ENDIF
\STATE res minCostsMatrix$[$i$][$j$]$
\end{algorithmic}
\end{algorithm}
\end{parr}

\textit{minCost} calcula el costo mínimo de un listón dado y su secuencia de cortes asociada, actualizando los datos en la matriz.\\

\begin{parr}
\begin{algorithm}[H]
\caption{\operL{minCost}{\vin{beginning}{int}, \vin{end}{int}}{int}}
\begin{algorithmic}[1]\parskip=1mm
\STATE min $\leftarrow \infty$
\STATE optimalCut $\leftarrow$ UNDEFINED
\STATE \textbf{//Se revisan todas la posibles particiones, recursivamente, buscando la de costo mínimo.}
\FOR {$k$ desde $(beginning + 1)$ hasta $(end - 1)$ }
\STATE int subRibbonsCost $\leftarrow$ calculateCost(beginning, k)	$+$ calculateCost(k, end)
\IF {subRibbonsCost $<$ min}
\STATE min $\leftarrow$ subRibbonsCost
\STATE optimalCut $\leftarrow$ k
\ENDIF
\ENDFOR
\STATE \textbf{//optimalCut es el corte óptimo, para este listón.}
\STATE \textbf{//se actualiza la secuencia de cortes, agregando a optimalCut como corte inicial, junto a los cortes óptimos de los sublistones.}
\STATE Vector$<$Integer$>$ newCutSequence $\leftarrow$ concatenar(minCostsMatrix$[$beginning$][$optimalCut$].optimalCuts$,
\STATE               													minCostsMatrix$[$optimalCut$][$end$].optimalCuts$)			             
\STATE minCostsMatrix$[$beginning$][$end$].optimalCuts $ $\leftarrow$ newCutSequence.AgregarAlPrincipio(cuts[optimaCut])
\STATE res $\leftarrow$ min
\end{algorithmic}
\end{algorithm}
\end{parr}


\newpage
\subsection{Demostración de la solución}
Para la demostración de correctitud, intentamos ver que se cumple el principio de optimalidad, es decir, que las subsoluciones óptimas, conforman a la solución total. Por induccion completa en la cantidad de cortes \textit{n} en un listón:
\begin{itemize}
\item Caso Base: $n = 0$ cortes en un liston, es decir, dos cortes consecutivos sin cortes en el medio:$\forall i M[i][i+1] = 0$, tal que  $0 \leq i, \leq n+1$, ya que en el listón, no hay cortes a realizar. Estas asignaciones se realizan al momento de inicializar la matriz, en la función \textit{initMatrix}.\\
\item Paso Inductivo: Queremos ver que para $n > 0$ el algoritmo es correcto. Usamos como hipótesis inductiva, que todos los sublistones con menos de \textit{n} cortes, están correctamente calculados en la matriz. Suponemos que tenemos un listón, que va desde el corte \textit{i} hasta el corte j y que tiene n cortes internos. Tambien sabemos que hay al menos un corte a realizar entre los cortes \textit{i,j}. Sabemos que el costo de realizar ese corte debe ser de $(j - i)$, ya que esa es la longitud del listón, y a eso se le suma los costos de las dos particiones resultantes óptimas, que combinadas dan el mínimo costo. Por hipótesis inductiva, estos costos son mínimos dentro de esos sublistones, y la partición elegida es la mínima, ya que se consideran todas las posibilidades de corte \textit{k} entre \textit{i,j}. $(\forall i, j$, tal que $j \geq i +2$,  $M[i][j] = cortes[j]-cortes[i] + min (M[i][k], M[k][j]) (\forall k$, $i < k < j))$

\item Al realizar estos cálculos, se mantiene actualizada la secuencia de cortes, para cada uno de los sublistones. De esta manera, al terminar los cálculos, sabemos que en la posición en el extremo superior derecho de la matriz ($M[0][n+1]$), podemos acceder tanto al costo mínimo como a la secuencia de cortes óptima entre los cortes \textit{0} y \textit{n+1}, que es otra forma de decir, el listón entero.\\
\end{itemize}
 
\subsection{Complejidad}
La complejidad del algoritmo es de orden cuadrado, ya que el costo de rellenar la matriz es de $(n+2)^2$ como máximo.
Mas en detalle:

\begin{itemize}

\item \textit{Ej3:} El costo de esta funcion es el costo de \textit{initMatrix} mas el costo de \textit{calculateCosts}.\\ Es decir, 
$T_{Ej3} = T_{initMatrix} + T_{calculateCosts}$.
\item \textit{initMatrix:} Esta función recorre e inicializa la matriz de $(n+2)*(n+2)$ dimensiones. Entonces la complejidad de initMatrix es $O(n^2)$.
\item \textit{calculateCosts:} Es el costo de calcular la complejidad temporal de $calculateCost(0,n+1)$.
\item \textit{calculateCost:} Si ya está calculado el costo en la posición \textit{i,j}, entonces será $O(1)$. Sino, $T_{calculateCost} = T_{minCost}$
\item \textit{minCost:} Sabemos que en el peor caso, el ciclo interno de minCost se ejecutará \textit{n} veces (siendo \textit{n} la cantidad de cortes). Dentro del mismo llama recursivamente a la función \textit{calculateCost} que es la que llenará la matriz con los diferentes resultados. En el peor caso (la primera vez), llena toda la matriz (lo que vale $n^2$). Las siguientes llamadas no tendrán que recalcular los resultados previamente calculados, pero aún así en peor caso tengo que pagar ese primer llenado. Luego la ejecución total del ciclo, la puedo acotar por $O(n^3)$.


%Sabemos que en el peor caso, el ciclo interno de minCost se ejecutará \textit{n} veces, siendo \textit{n} la cantidad de cortes. 
%La doble llamada recursiva en la línea \textit{(5)} del pseudocódigo, indica que se ejecutará el mismo mismo ciclo recursivamente, pero en cada ciclo, la cantidad de operaciones es cada vez, menor. Se puede acotar superiormente estas ejecuciones por $n^2$. \\

Mas adelante, en las líneas \textit{(13)}, \textit{(14)} y \textit{(15)}, se concatena dos vectores, agregando luego un elemento mas al vector resultante. Este vector, es un vector que almacena una secuencia de cortes, con lo que la longitud de este vector (y su complejidad), no pueden superar a \textit{n}. Ademas, por como funciona el algoritmo, solo se usará la mitad de las posiciones de la matriz, las posiciones de la parte triangular superior.\\

\item De todos estos cálculos, se deduce que la complejidad del algoritmo es de orden \textbf{$O(n^3)$} para un listón de $n$ cortes.

\end{itemize}

\subsection{Tests}
Para realizar los tests, se hicieron pruebas con instancias cuyos cortes fueron distribuidos aleatoriamente a lo largo del listón. Por simplicidad, se decidió fijar la longitud del listón en $1000$ para todas las instancias de prueba.\\
Cuando nos ponemos a pensar algún ``mejor caso"" o ``peor caso" para el algoritmo, cuesta encontrarlo ya que si fijamos una cantidad de \textit{n} cortes y un listón de longitud \textit{l}, sabemos o suponemos, que independientemente de la distribución de los cortes, las operaciones de cálculo para hallar la solución deseada no varía. Es decir, siempre estaremos realizando una determinada cantidad de cálculos en la matriz con un \textit{n} fijo.\\Con los tests, intentaremos ver si esto es cierto.

\subsection{Gr\'aficos}




\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej3/random.pdf,width=0.9\linewidth,clip=}
\caption{Test sobre valores Random.}
\end{figure}

Como se puede ver en la figura, el resultado de las mediciones, se asemeja a la complejidad teórica calculada. Se ve que buscando un coeficiente adecuado para la función cúbica, se puede acotar a la curva formada por los puntos resultantes de las mediciones. En este caso, las instancias eran listones de longitud $1000$, con cortes desde $3$ hasta $80$.



\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej3/samecuts.pdf,width=0.9\linewidth,clip=}
\caption{Tests para un conjunto de instancias con misma longitud del liston y misma cantidad de cortes.}
\end{figure}




El resultado de este gráfico muestra que para instancias generadas de manera aleatoria, teniendo valores fijos para la longitud del listón, y la cantidad de cortes a realizar, la diferencia en la medición del costo de ejecución es prácticamente mínima. Esto nos sugiere el hecho de que en este problema particular, no hay un ``mejor caso" o ``peor caso"", ya que la naturaleza del problema así lo muestra.

\subsection{Conclusiones}
El algoritmo propuesto usa la técnica de programación dinámica para calcular la secuencia de cortes de costo mínimo. El método utilizado no es intuitivo a simple vista, pero utiliza el concepto del principio de optimalidad exitosamente, haciendo uso de la recursividad presente en todo algoritmo que usa ésta técnica. A pesar de estar usando solo la mitad de la matriz, sabemos que calcular 2 veces el costo para cada sublistón implicaría que el tiempo de ejecución se vería prácticamente doblado.\\